package bTree.LeetCode;

import java.security.ProtectionDomain;

public class 删除二叉搜索树中的节点   {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
             this.left = left;
             this.right = right;
         }
      }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root==null){
            return null;
        }
        if (root.val==key){
            //1.左右都不为空，一钟方法是把右节点拼接到左节点最右子树的右子树
            if (root.left!=null&&root.right!=null){
                TreeNode left = root.left;//左节点
                TreeNode right = root.right;//右节点
                TreeNode p=left;
                while (p.right!=null){
                    p=p.right;
                }
                p.right=right;
                return left;
            }
            //2.都为空
            if (root.left==null&&root.right==null){
                return null;
            }
            //3.左或者右为空
            if (root.left==null){
                return root.right;
            }
            if (root.right==null){
                return root.left;
            }
        }
        root.left = deleteNode(root.left, key);
        root.right = deleteNode(root.right, key);
        return root;
    }
}